import math
import random
import string


def neatly_print(length, n, m):
    line_extra = [[] for _ in range(n)]
    for i in range(n):
        line_extra[i][i] = m - length[i]
        for j in range(i + 1, n):
            line_extra[i][j] = line_extra[i][j - 1] - length[i] - 1
    num = float("inf")
    line_cubes = [[] for _ in range(n)]
    for i in range(n):
        for j in range(i, n):
            if line_extra[i][j] < 0:
                line_cubes[i][j] = num
            elif j == n:
                line_cubes[i][j] = 0
            else:
                line_cubes[i][j] = math.pow(line_extra[i][j], 3)
    cubes = []
    p = []
    cubes[0] = 0
    for j in range(n):
        cubes[j] = num
        for i in range(j):
            if line_cubes[i][j] + cubes[i - 1] < cubes[j]:
                cubes[j] = line_cubes[i][j] + cubes[i - 1]
                p[j] = i
    return cubes, p


def print_word(p, n):
    if n == 0:
        return
    print_word(p, p[n] - 1)
    print(p[n], n)


def generate_random_str(randomlength: int) -> string:
    """
    生成一个指定长度的随机字符串，其中
    string.digits=0123456789
    string.ascii_letters=abcdefghigklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ
    """
    str_list = [random.choice(string.digits + string.ascii_letters)
                for _ in range(randomlength)]
    random_str = ''.join(str_list)
    return random_str


def generate_random_str_list() -> list[str]:
    """
    :return:
    """
    count = int(input("请输入字符串数量:"))
    lenth_max = int(input())
    randomlist = random.sample(range(5, lenth_max), count)
    str_list = []
    for lenth in randomlist:
        str_list.append(generate_random_str(lenth))
    return str_list


if __name__ == '__main__':
    # k, j = test()
    # print("%d  %d" % (k, j))
    n = int(input())
    m = int(input())
    in_str = generate_random_str_list()
    length = []
    for item in in_str:
        length.append(len(item))
    cubes, p = neatly_print(length, n, m)
    print_word(p, n)
    # print(generate_random_str_list())
